#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: graph_bfs.py 
@version:
@time: 2024/01/27 

1. 选择一个初始节点入队，并在visited数组中将此节点所在位置标记为1，本实例选择节点1
2. 进入循环迭代，只要队列不为空，弹出队头元素并输出，即节点1；然后将节点1的所有相邻接而且未被访问过的节点依次入队，即节点2、4、5；
并在visited数组中将入队元素所对应位置标记为1.
3. 节点2出队并输出，与节点2相连且未被访问过的节点只有节点3，将其入队。
4。 依次将节点4,5,3出队即可完成广度优先搜索过程
"""
from collections import deque


class GGraph:

    def __init__(self, _point, _graph):
        self.graph = _graph
        self.point = _point
        self.visited = [0] * len(_graph)

    def bfs(self, n):
        queue = deque([n])
        self.visited[n] = 1
        while queue:
            node_index = queue.popleft()
            print(self.point[node_index])
            for i in range(len(self.graph)):
                if self.graph[node_index][i] == 1 and self.visited[i] == 0:
                    queue.append(i)
                    self.visited[i] = 1


graph = [
    [0, 1, 0, 1, 1],
    [1, 0, 1, 0, 0],
    [0, 1, 0, 0, 0],
    [1, 0, 0, 0, 1],
    [1, 0, 0, 1, 0],
]

point = [1, 2, 3, 4, 5]
GGraph(point, graph).bfs(0)
